package com.Expression;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 逆波兰表达式计算器
 *
 */
public class PolandNotation {
    public static void main(String[] args) {
//        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
//        int res = getSuffixResult(suffixExpression);
//        System.out.println(res);
        String infixExp="1+((2+3)*4)-5";
        String suffix = infixToSuffix(infixExp);
        int result = getSuffixResult(suffix);
        System.out.println(suffix+" = "+ result);
    }



    /**
     * 对表达式进行计算，从左至右扫描表达式，遇到数字进行入栈，遇到运算符则将数字出栈并进行运算，将运算结果存入栈中
     * 1.将表达式放入ArrayList中
     * 2.将ArrayList传给方法进行遍历，配合栈进行计算
     */
    public static int getSuffixResult(String suffixExp){
        /*
        将suffixExp进行分割用数组存储，再将数组转换
        数组转ArrayList : List<String> list = new ArrayList<>(Arrays.asList(split));
        ArrayList转数组 : String[] strArray = new String[list.size()];  list.toArray(StrArray);
         */
        String[] split = suffixExp.split(" ");
        List<String> suffixList = new ArrayList<>(Arrays.asList(split));

        //只需要一个栈进行存放数字即可
        Stack<String> numStack = new Stack<String>();
        //遍历集合中的运算
        for (String item: suffixList ) {
            //通过正则表达式获取集合中的元素
            if( item.matches("\\d+")){
                numStack.push(item);
            }else {
                //运算一定是后弹出的元素作用先弹出的元素
                int num1 = Integer.parseInt(numStack.pop());
                int num2 = Integer.parseInt(numStack.pop());
                int res = 0;
                char key = item.charAt(0);
                switch (key){
                    case '+':
                        res = num2 + num1;
                        break;
                    case '-':
                        res = num2 - num1;
                        break;
                    case '*':
                        res = num2 * num1;
                        break;
                    case '/':
                        res = num2 / num1;
                        break;
                    default:
                        throw new RuntimeException("运算符有误!");
                }
                //int转String三种方法: String.valueOf(i); / Integer.toString(i) / i+""
                numStack.push(res+"");
            }
        }
        //最后留在栈中的即为运输结果
        return Integer.parseInt(numStack.pop());
    }
    /*
    1. 建立符号栈
    2. 顺序扫描中序表达式
    a）是数字，直接输出
    b）是运算符
      i : “(” 直接入栈
     ii : “)” 将符号栈中的元素依次出栈并输出, 直到 “(“, “(“只出栈, 不输出
     iii: 其他符号, 将符号栈中的元素依次出栈并输出, 直到遇到当前元素比栈顶元素符号优先级更高时或者”(“。 将当前符号入栈。
    3. 扫描完后, 将栈中剩余符号依次输出
     */
    public static String infixToSuffix(String infixExp){
        //3+(20-5)*6/3
        String suffixExp = "";
        //将表达式放入到ArrayList中进行操作
        Stack<String> stack = new Stack<>();
        int index = 0;
        while(index < infixExp.length()){
            String str = infixExp.substring(index,index+1);
            //判断是否运算符,通过正则表达式匹配是否为"+ - * / ( )"中的其中一个
            if(str.matches("[+-/*/()]")){
                if("(".equals(str)){
                    stack.push(str);
                }else if(")".equals(str)){
                    while(!("(".equals(stack.peek()))){
                        String pop = stack.pop();
                        suffixExp += pop.concat(" ");
                    }
                    stack.pop();
                }else {
                    if(stack.isEmpty()){
                        stack.push(str);
                    }else {
                        while((priority(str)) <= (priority(stack.peek()))){
                            String pop = stack.pop();
                            suffixExp += pop.concat(" ");
                            if(stack.isEmpty()){
                                break;
                            }
                        }
                        stack.push(str);
                    }
                }
            }else {
//                if(index == suffixExp.length() -1){
                    suffixExp += str.concat(" ");
//                }else {
//                    if(suffixExp.substring(index,index+1).matches("[0-9]]"));
//                }
            }
            index++;
        }
        //扫描完成后将符号栈中的符号依次出栈
        while (!stack.isEmpty()){
            String s = stack.pop();
            suffixExp += s;
        }
        return suffixExp;
    }


    /**
     * 返回运算符优先级，优先级用数字来表示，数字越大表示优先级越高
     */
    /*
     * 错误：在比较oper的值时写成"-" == oper
     * 总结：==比较基本数据类型时为比较值，比较引用数据类型时为比较内存地址
     * 在比较String类型时有两种情况：如果是两个常量进行比较，则比较两个常量的值，因为常量时放在常量池中的，在常量池中查看是否有相同的值来判断
     * 如果比较的操作数中有个为对象时，则比较两个操作数的内存地址
     * oper为对象，和“-”进行比较内存地址全为false，所以返回-1
     * 这里改成equals方法比较值(String中重写了equals方法
     */
    public static int priority(String oper){
        if("*".equals(oper) || "/".equals(oper)){
            return 1;
        }else if("+".equals(oper) || "-".equals(oper)){
            return 0;
        }else {
            return -1;
        }
    }

}
